import java.util.ArrayList;
import java.util.EmptyStackException;
import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 17655
 * Date: 2025-06-06
 * Time: 19:58
 */
public class test3 {
    public static ArrayList<Integer> evaluate(String expression) {
        char[] tokens = expression.toCharArray();

        // 栈用于存储数字
        Stack<Integer> values = new Stack<>();
        // 栈用于存储运算符
        Stack<Character> ops = new Stack<>();

        // 顺序表用于存储中间结果和最终结果
        ArrayList<Integer> resultSequence = new ArrayList<>();

        for (int i = 0; i < tokens.length; i++) {
            if (Character.isDigit(tokens[i])) {
                // 如果是数字，计算完整的数字（处理多位数）
                int num = 0;
                while (i < tokens.length && Character.isDigit(tokens[i])) {
                    num = num * 10 + (tokens[i] - '0');
                    i++;
                }
                i--; // 因为循环结束后 i 多加了 1，所以减回来
                values.push(num);
                resultSequence.add(num); // 将数字加入顺序表
            } else if (tokens[i] == '(') {
                // 如果是左括号，压入运算符栈
                ops.push(tokens[i]);
            } else if (tokens[i] == ')') {
                // 如果是右括号，弹出并计算直到遇到左括号
                while (ops.peek() != '(') {
                    int result = applyOp(ops.pop(), values.pop(), values.pop());
                    values.push(result);
                    resultSequence.add(result); // 将中间结果加入顺序表
                }
                ops.pop(); // 弹出左括号
            } else if (tokens[i] == '+' || tokens[i] == '-' || tokens[i] == '*' || tokens[i] == '/') {
                // 如果是运算符，弹出并计算所有优先级更高的或相等的运算符
                while (!ops.isEmpty() && hasHigherOrEqualPriority(ops.peek(), tokens[i])) {
                    int result = applyOp(ops.pop(), values.pop(), values.pop());
                    values.push(result);
                    resultSequence.add(result); // 将中间结果加入顺序表
                }
                ops.push(tokens[i]);
            }
        }

        // 处理剩余的运算符
        while (!ops.isEmpty()) {
            int result = applyOp(ops.pop(), values.pop(), values.pop());
            values.push(result);
            resultSequence.add(result); // 将最终结果加入顺序表
        }

        return resultSequence;
    }

    // 判断运算符 op1 是否比 op2 优先级高或相等
    private static boolean hasHigherOrEqualPriority(char op1, char op2) {
        if (op1 == '(' || op1 == ')') {
            return false;
        }
        if ((op1 == '*' || op1 == '/') && (op2 == '+' || op2 == '-')) {
            return false;
        }
        return true;
    }

    // 应用运算符
    private static int applyOp(char op, int b, int a) {
        switch (op) {
            case '+':
                return a + b;
            case '-':
                return a - b;
            case '*':
                return a * b;
            case '/':
                if (b == 0) {
                    throw new UnsupportedOperationException("Cannot divide by zero");
                }
                return a / b;
        }
        return 0;
    }

    public static void main(String[] args) {
        String expression = "(10 + 2) * 3 - 5 / (14 - 12)";
        try {
            ArrayList<Integer> resultSequence = evaluate(expression);
            System.out.println("Expression: " + expression);
            System.out.println("Result Sequence: " + resultSequence);
        } catch (EmptyStackException e) {
            System.out.println("Invalid expression");
        } catch (UnsupportedOperationException e) {
            System.out.println(e.getMessage());
        }
    }
}
